| Algorithms and Data Structures in C++ by Alan Parker CRC Press, CRC Press LLC ISBN: 0849371716 Pub Date: 08/01/93

Previous | Table of Contents | Next

## Chapter 2
Algorithms

This chapter presents the fundamental concepts for the analysis of algorithms.

### 2.1 Order

N denotes the set of natural numbers, {1, 2, 3, 4, 5, . . .}.

Definition 2.1

A sequence, x, over the real numbers is a function from the natural numbers into the real numbers:

x1 is used to denote the first element of the sequence, x(1) In general,

and will be written as

Unless otherwise noted, when x is a sequence and f is a function of one variable, f(x), is the sequence obtained by applying the function f to each of the elements of x. If

then

For example,

Definition 2.2

If x and y are sequences, then x is of order at most y, written x ∈ O (y), if there exists a positive integer N and a positive number k such that

Definition 2.3

If x and y are sequences then x is of order exactly y, written, x ∈ Θ (y), if x ∈ Θ (y) and y ∈O (x).

Definition 2.4

If x and y are sequences then x is of order at least y, written, x ∈ Ω (y), if y ∈ O (x).

Definition 2.5

The time complexity of an algorithm is the sequence

where tk is the number of time steps required for solution of a problem of size k.

Example 2.1 Time Complexity

The calculation of the time complexity for addition is illustrated in Example 2.1. A comparison of the order of several classical functions is shown in Table 2.1. The time required for a variety of operations on a 100 Megaflop machine is illustrated in Table 2.2. As can be seen from Table 2.1 if a problem is truly of exponential order then it is unlikely that a solution will ever be rendered for the case of n=100. It is this fact that has led to the use of heuristics in order to find a “good solution” or in some cases “a solution” for problems thought to be of exponential order. An example of Order is shown in Example 2.2. through Example 2.4.

Table 2.1 Order Comparison
Function | n=1 | n=10 | n=100 | n=1000 | n=10000
--- | --- | --- | --- | --- | ---
log(n) | 0 | 3.32 | 6.64 | 9.97 | 13.3
nlog (n) | 0 | 33.2 | 664 | 9.97×103 | 1.33×105
n2 | 1 | 100 | 10000 | 1×106 | 1×108
n5 | 1 | 1×105 | 1×1010 | 1×1015 | 1×1020
en | 2.72 | 2.2×104 | 2.69×1043 | 1.97×10434 | 8.81×104342
n! | 1 | 3.63×106 | 9.33×10157 | 4.02×102567 | 2.85×1035659

Table 2.2 Calculations for a 100 MFLOP machine
Time | # of Operations
--- | ---
1 second | 108
1 minute | 6×109
1 hour | 3.6×1011
1 day | 8.64×1012
1 year | 3.1536×1015
1 century | 3.1536×1017
100 trillion years | 3.1536×1029

#### 2.1.1 Justification of Using Order as a Complexity Measure

One of the major motivations for using Order as a complexity measure is to get a handle on the inductive growth of an algorithm. One must be extremely careful however to understand that the definition of Order is “in the limit.” For example, consider the time complexity functions f1 and f2 defined in Example 2.6. For these functions the asymptotic behavior is exhibited when n ≥ 1050. Although f1 ∈ Θ (en) it has a value of 1 for n < 1050. In a pragmatic sense it would be desirable to have a problem with time complexity f1 rather than f2. Typically, however, this phenomenon will not appear and generally one might assume that it is better to have an algorithm which is Θ (1) rather than Θ (en). One should always remember that the constants of order can be significant in real problems.

Example 2.2 Order

Example 2.3 Order

Previous | Table of Contents | Next

Copyright © CRC Press LLC